1. Field of the Invention
The present invention relates generally to fault recovery methods, and more particularly to a path establishment method for a meshed network that can be recovered from failure using different fault recovery types.
2. Description of the Related Art
In a public communication network, fault recovery is an indispensable task. Meshed network configuration has met with wide acceptance because of its versatile fault recovery features. A fault recovery method using GMPLS (Generalized Multi-Protocol Label Switching) technology in a mesh network is described in an Internet Draft “Generalized Multi-Protocol Label Switching (GMPLS) Architecture”, draft-ietf-ccamp-gmpls-architecture-01.txt which Eric Mannie submitted in IETF (Internet Engineering Task Force) (hereinafter Document 1). According to Document 1, chapter 12, a fault recovery method is classed in protection and restoration modes. In the protection mode, a failure is restored by allocating a backup resource well in advance of a possible failure and with this pre-allocation no signaling procedure is required. The fault section is simply restored by operating a switch. On the other hand, the restoration mode is one in which no backup resources are allocated in advance. When a failure occurs, signaling is used to exchange messages between the edge points of the fault section in order to allocate a backup resource for restoration. The fault recovery is classified between a link-by-link recovery method and a recovery method based on a per LSP (Label Switched Path) which is identified by a label in a GMPLS network. Furthermore, the fault recovery method is classified according to the redundancy of backup resources into “1+1”, “1:1” “1:N” and “M:N” in that order. Recovery type “1+1” is usually applied to the protection mode in which a protection resource is allocated to a working resource and the signal of the working resource is also supplied at the upstream end of the protection resource. When the working resource fails, the downstream end of the protection resource is switched to pass the signal downstream. Recovery type “1:1” is applied to both protection and restoration modes. In this type of recovery, a protection resource is allocated to a working resource. However, the signal is not supplied to the protection resource. When the working resource fails, both the upstream and downstream ends of the protection resource are switched to carry the signal. When the working resource is normal, the protection resource is used to carry an extra traffic. This extra traffic is shut down when the protection resource is switched in to carry the main signal. Recovery type “1:N” is also applied to both protection and restoration modes. This recovery type differs from “1:1” recovery type in that N protection resources are shared by a single working resource. Recovery type “M:N” is a special case of recovery types “1:1” and “1:N”, and when N is more than one, the recovery type M:N is called “Shared”. By setting N larger than M, resource utilization efficiency can be enhanced. However, simultaneous occurrences of failures in both working and protection resources means that the system cannot be recovered and hence it is necessary to guarantee that probability of fault occurrences in the protection resources is significantly low.
In order to guarantee that shared resources have a low fault occurrence rate, a concept of shared risk link group (SRLG) has been introduced. In a wavelength multiplex network, wavelength channels that share the same optical fiber, or optical fibers that share the same cable, or optical fibers connected to the same node, are treated as a common SRLG and identified uniquely in a network by an SRLG identifier. There may be instances where a single link belongs to a number of different SRL groups.
In a GMPLS network, a list of SRLG identifiers is maintained for each link of the network that belongs to the SRL groups of the list. Two paths are said to be SRLG-disjoint if their links belong to different sets of shared risk link groups in each of which any one of the links do not overlap any one of the other group. If one of the SRL groups fails, the SRLG-disjoint paths never fail simultaneously.
Shared restoration for restoring a single SRLG failure by using GMPLS is disclosed in internet draft submitted to IETF “RSVP-TE Extensions for Shared-Mesh Restoration in Transport Network”, draft-li-shared-mesh-restoration-01.txt (Document 2), Guangzhi Li et al. According to Document 1, Document 2 can be classified under “End-to-end LSP restoration with pre-signaled recovery bandwidth reservation and no label pre-selection”.
According to Document 2, when a path setup request is generated, the network calculates a pair of SRLG-disjoint working and protection paths. A signaling message is then transmitted through the network. In this process, bandwidth reservation is performed for both working and protection paths. However, label assignment and connection establishment are performed only on the working path. If the working path fails, a signaling message will be transmitted along the route of the reserved protection path to perform label assignment and connection establishment. In order to guarantee fault recovery of a single SRL group, two techniques are used in this prior art. One is to append a list of SRLG identifiers to a signaling message for establishing the protection path. In this list, all SRL groups to which the links of the working path belong are indicated. The other is to manage the reservation bandwidth of each link with a reservation array R [i] (where i represents SRLG ID) for each SRL group. The management of a reservation array R [i] is essentially the management of a protection path according to different SRL groups of the working path. Specifically, if a working path of a 10-Gbps bandwidth uses links that belong to a list of shared risk link groups identified by SRLG ID's 1, 3, 5, a list of SRLG identifiers 1, 3 and 5 is appended to a signaling message when establishing a protection path when that working path fails. Nodes along the route of the protection path adds 10 Gbps to the links R [1], R [3] and R [5] of the protection path. If the maximum value Max (R [i]) is greater than the maximum bandwidth of the links, the protection path is not established. Since R [i] represents the bandwidth required for a link that belongs to SRLG ID=i, a single SRLG failure can be restored in so far as Max (R [i]) is smaller than the maximum bandwidth of the link. This recovery method can be classified as a shared recovery type M:N, since all protection paths that pass through a link share the same bandwidth of Max (R [i]).
To seek a shortest path in GMPLS, use is made of a route calculation algorithm known as CSPF (Constrained Shortest Path First) which applies the Dijkstra algorithm to a set of links that satisfy a set of constraints, such as SRLG disjoint between working and protection paths and a constraint that a link whose unreserved bandwidth be greater than the bandwidth of a path. Application of a constraint guarantees that a required bandwidth can be secured on each link of a calculated route. According to Document 2, the maximum value R [i] is the whole bandwidth reserved by protection paths. By subtracting the bandwidths assigned to both working and protection paths from the bandwidth of a link, unreserved bandwidth can be determined.
However, the prior art route calculation and fault recovery algorithms do not allow a number of communication channels of different fault recovery types to be accommodated in a single communications network for a number of reasons. For example, fault recovery type 1+1 allows fast recovery from failure, but it needs the same amount of backup resource for a protection path as that of its working path and does not allow the protection path to carry extra traffic. Shared recovery type, though taking a longer time than 1+1 to recover and not capable of recovering from multiple failures, allows backup resources to be shared among working resources and extra traffic to be accommodated. Shared recovery type has the highest resource utilization efficiency. Since the grade of service as represented by the fault recovery time and the recovery rate contradicts with resource utilization efficiency, the prior art has employed different fault recovery types for different grades of service.
If a number of different fault recovery types coexist in a single network, there is a need to perform priority control. The 1+1 recovery type is assigned higher priority over 1:1, which should be assigned higher priority over the shared type, and if multiple failures should occur, fault recovery should be performed in that order.
Another problem is that the constraint route calculation algorithm is not appropriate for extra traffic since it can result in a situation where extra traffic is set up over links where 1:1 or shared type protection paths are not established.
In the fault recovery aspect of a communications network, time-slot fragmentation is still another problem. A path cannot be established on a TDM link if the bandwidth of this path is greater than that of each of fragmented time-slots. For fault recovery purposes, fragmented time-slots cannot be concatenated. In Document 2, R [i] is managed on a link-by-link basis and a protection path is established on a link if the maximum value of R [i] does not exceed some threshold which is equal to the difference between the bandwidth of the link and the bandwidth of a working path accommodated in the link. If time-slot fragmentation occurs on a TDM link, a protection path cannot be established on the link in the event of a failure even if the maximum value of R [i] is lower than the threshold value.